package sort.leetcode.hard;

import java.util.*;

/**
 * @author bruin_du
 * @description 数据流中的中位数
 * @date 2022/5/31 16:08
 **/
public class Offer41_MedianFinder {
    //两个优先级队列：小顶堆和大顶堆
    //小顶堆中保存较大的一半数据,大顶堆中保存较小的一半数据
    //两个堆大小不相等时,说明数据为奇数个,先往大顶堆中填入数据取出最大值填入小顶堆
    //两个堆大小相等时,说明数据个数为偶数,先玩小顶堆中插入数据,取出最小值往大顶堆中插入
    //取出数据的就按两个堆大小是否相等取出
    Queue<Integer> sQueue,bQueue;
    public Offer41_MedianFinder() {
        sQueue = new PriorityQueue<>();
        bQueue = new PriorityQueue<>((x,y)->(y - x));
    }

    public void addNum(int num) {
        if(sQueue.size() != bQueue.size()){
            sQueue.offer(num);
            bQueue.offer(sQueue.poll());
        }else{
            bQueue.offer(num);
            sQueue.offer(bQueue.poll());
        }
    }

    public double findMedian() {
        return sQueue.size() != bQueue.size() ? sQueue.peek() : (bQueue.peek() + sQueue.peek()) / 2.0;
    }
}
